import java.util.Stack;

/**
 * @author LKQ
 * @date 2021/12/26 20:27
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        ListNode l5 = new ListNode(5), l4 = new ListNode(4, l5), l3 =
                new ListNode(3, l4), l2 = new ListNode(2, l3), l1 =
                new ListNode(1, l2);
        Solution solution = new Solution();
        ListNode l6 = new ListNode(1);
        solution.removeNthFromEnd2(l1, 2);
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = head;
        Stack<ListNode> stack = new Stack<>();
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        ListNode deleteNode = null;
        while (n > 0) {
            deleteNode = stack.pop();
            n--;
        }
        ListNode root = new ListNode(0, head);
        ListNode t = root;
        while (t != null) {
            ListNode pre = t;
            if (pre.next == deleteNode) {
                pre.next = pre.next.next;
                break;
            }
            t = t.next;
        }
        return root.next;
    }
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode temp = head;
        int k = 0;
        while (temp != null) {
            k++;
            temp = temp.next;
        }
        ListNode root = new ListNode(0, head);
        ListNode t = root;
        while (t != null) {
            ListNode pre = t;
            if (k-- == n) {
                pre.next = pre.next.next;
                break;
            }
            t = t.next;
        }
        return root.next;
    }
}
